Vector quantization is a type of quantization in which a set of samples conveiently extracted from the signal to be coded is taken into account, instead of a single sample. For example, in the case of image signals, the matrix formed by the samples obtained from the signal by orthogonal sampling is scanned by rows and samples are extracted from a number of rows successive in time (e.g. two or four samples for each of two successive rows, or four samples for each of four successive rows) are quantized together. Blocks of 2.times.2, 2.times.4 or 4.times.4 samples, respectively, are thus obtained.
Considering, for example, the 2.times.4 case, if the samples are represented by 8 bits (corresponding to 256 quantization levels per sample), as stated in CIRR recommendation 601, the number of possible configurations is 256 .sup.8, which must be represented by 64 bits.
Through vector quantization techniques the number of possible configurations is reduced and becomes variable, typically within 1024 and 128; if the configurations are equiprobable, just 10 and 7 bits are required for their representation.
Vector quantization is a potentially better algorithm than others, since it not only permits considerable redundancy reduction, but is also allows exploitation of statistical dependency amon the variables to be coded (in this case the image points) and not only to correlation; yet its implementation gives rise to two problems.
The first problem concerns codebook generation, i.e. the indentification, based upon a particular distortion minimization criterion, of the most probable values of the set of variables, namely identification of the regions of an n-dimensional space, where higher values density exists. In this particular case the 1024 or 128 configurations (or code vectors) representing the possible 256.sup.8 quantized signal configurations, are to be obtained.
The second problem concerns the identification of the vector to be used for representation of the generic block, always taking into account the distortion minimizations criterion.
A known solution to the codebook generation problem is described by Y. Linde, A Buzo and R.M. Gray in the paper entitled "An Algorithm for Vector Quantizer Design", IEEE Transactions on Communications, Vol. Com-28, No.1, Jan. 1980.
This paper describes an iterative algorithm which, in the most usual application, computes in a first step the centroid of the set of the vectors relevant to a sequence of training signals. The centroid is then multiplied by a scalar quantity thus identifying non-optimized representative points of two hypothetical classes of such a set. By use of these two representative classes, this set is partioned, allotting each of the vectors to either calss. As a third step, the actual centroid of each of the two classes obtained is calculated. The same operations are repeated for the two new centroids and so on until the desired number of representative vectors is obtained.
Once the codebook is built up, the actual coding can be effected either by comparison of each vector to be coded with all the representative vectors and consequent choice of the one which minimzes the distortion, or by a selective tree technique.
This known method can be applied whatever distortion criterion is to be satisfied. However, the codebook generation method is particularly inefficient due to the large number of operations to be performed on the training sequence, and is also rather complicated since the analysis on the set is performed in an n-dimensional space. The coding phase, if the comparison technique is chosen, is very time consuming due to the necessity of making comparisons with the whole codebook, and does not allow direct identification of the vector representative of the block to be coded. In the case of a selective tree technique, the number of comparisons is reduced, but optimal representation is not ensured.